CD Actual 1/PC Actual CD 01.iso/share/dos/demos/planets/doc.lzh/PLANET.MS

Text File | 1994-05-01 | 41.5 KB | 1,093 lines

.\"
.\" Planet Animation
.\" This is input data for the 'troff' text formatter (with ms macros)
.\"
.ds RH Planet Demo
.^b HF 1
.^b fh 0
.TL
The Definitive Guide to Bouncing Planets
(a document with a modest title)
.AU
Simon Hern
.AI
22 Harrington Drive
Bedford MK41 8DB
England
.AB
This document describes how to create a computer animation of a
rotating planet using simple texture-mapping techniques. It should make
an interesting programming project for someone with a basic knowledge of
assembly language and computer graphics.
.AE
.LD
August, 1992
Revised December, 1992
Revised April, 1994
.DE
.sp 3
.NH 1
Introduction
.NH 2
Planets, Past and Present
.PP
In the spring of 1990 a computer animation of a rotating planet lived
out a brief, anonymous but happy existence. Years have passed.
Now here's the sequel.
.PP
The greatest improvement of this program over the hacked-together-in-Basic
original is the neatness and completeness of its design.
More interesting improvements are:
.RS
.IP *
Faster animation techniques.
.IP *
Choice of planet sizes and axes of rotation.
.IP *
Generation of semi-convincing planet surfaces.
.IP *
Illumination effects.
.RE
.PP
The makers of the original 'Star Trek' would've died to use this animation
as a special effect. That's how good it is.
.NH 2
Disclaimers and Apologies
.PP
There are a few things I ought to mention before going on.
.PP
Firstly, I am by no stretch of the imagination an expert in computer
graphics, or for that matter computer programming of any description.
Nearly all of what follows I figured out for myself during boring physics
lessons (something I've always felt quite proud of). If there are any
books that describe how to do this sort of thing, I've never seen them
(though I would certainly like to).
.PP
Secondly, a work of stunning originality this isn't. When I started this
project I had never seen or heard of anything like it. But that was
probably more by chance than anything else since I've now had reports of
people writing spinning planet animations (along very similar lines to what
I'm describing here) as far back as the mid-eighties.
.PP
Finally, I must apologize for the naming of some of the concepts
described here (Gush, Complexion, Riff, etc). They are not technical terms,
merely the inventions of a warped mind (I was reading a lot of Clive
Barker books at the time).
.PP
That's enough of that. Now on with the show.
.NH 2
Overview of the Program
.PP
The planet program divides up into three basic segments which I will cover
(in long-winded detail) in turn.
.PP
The first part of the program creates a large array of data called the Gush
which is required for the rapid animation of the planet. See Section
2.
.PP
The second part of the program generates a random surface for the planet
and gives it colour. The resulting data array is called the Complexion.
See Section 3.
.PP
The third part of the program uses these two data arrays to
animate the planet in real time. For each frame of animation
the entire planet is redrawn, rotated as required. See Section 5.
.PP
Sections 4 and 6 contain details on how the animation can be implemented
in practice.
.NH 2
Planet Shapes and Sizes
.PP
The following constant values appear in various places throughout the
program. They control certain aspects of the planet's appearance.
.IP \fIRADIUS\fR 8
This (integer) value is the radius in pixels of the planet as it
appears on the screen.
.IP \fIDIST\fR 8
This is the apparent distance of the observer from the planet.
It is measured in pixels from the planet's centre and would usually take
a value in the order of several times the width of the screen. It must
have a value greater than that of \fIRADIUS\fR. (The effect this value has
is, to be honest, pretty minimal.)
.IP \fIrho\fR 8
This value (an integer) is the resolution of the planet's surface.
It is the number of points of latitude (north to south) and half the number
of points of longitude (around the equator) used when giving coordinates to
the landscape.
.IP \fIphi\fR 8
This is the angle through which the axis of rotation of the planet is tilted
backwards from the vertical (as seen by the observer).
.IP \fItheta\fR 8
This is the angle through which the axis of rotation of the planet is turned
clockwise (as seen by the observer).
.PP
\fIphi\fR and \fItheta\fR do not need to be in any particular
units since it is their sines and cosines that are required and the units
conversion can take place when these are calculated.
.PP
These constants will be discussed in more detail as they are used.
.NH 1
Writing the Gush: Data for Spinning a Planet
.NH 2
From Screen to Surface
.PP
A lot of calculations need to be performed before drawing a planet.
To speed up the animation procedure, the results of most of these
calculations are worked out in advance and stored in a data array which I
call the Gush.
The Gush consists of data for transforming points of the planet as
seen on the screen to points on the mercator map of the planet's surface.
.PP
Two stages are required to create the Gush. The first stage
considers the Gush as a two-dimensional grid (the Square Gush), with
each point corresponding to a pixel on the screen,
and performs the lengthy floating-point calculations.
In the second stage the data in the Gush is rearranged to make it more
readily accessable to the animation routines. This second stage Gush is
called the Line Gush.
.NH 2
Constants and the Gush
.PP
All of the constants described in Section 1.4 are referred to in the Gush
calculations.
.PP
It is worth noting that the values of
\fIDIST\fR, \fIphi\fR, \fItheta\fR and (possibly) \fIRADIUS\fR
are needed only when creating the Gush and will probably not appear
anywhere else in the program. As a result, Gushes created using different
values for these constants can be used interchangeably.
.NH 2
The Square Gush
.PP
The Square Gush is an array of size \fI2*RADIUS\fR by \fI2*RADIUS\fR and is
referenced by variables \fIxs\fR and \fIys\fR, both of which take values
from \fI0\fR to \fI2*RADIUS-1\fR.
Each entry in the array holds two values: \fIxm\fR and \fIym\fR,
both non-negative integers of size depending on the choice of \fIrho\fR.
.PP
The array will be described using the notation \fIgush[ys][xs].xm_val\fR
and \fIgush[ys][xs].ym_val\fR to mean the values of \fIxm\fR and \fIym\fR
at the (\fIxs,ys\fR) position in the array.
.PP
The points of the Square Gush correspond directly to the pixels of the
planet's image on the screen; the empty space around the planet is
represented by null values in the array.
.PP
The values of \fIxm\fR and \fIym\fR for a point (\fIxs,ys\fR)
are calculated in the following way.
.PP
First, define a new constant, \fIg\fR, as
.CD
.I
g = DIST * RADIUS / sqrt( DIST*DIST + RADIUS*RADIUS )
.R
[\fIsqrt()\fR meaning 'square root']
.PP
Next, to make the calculations faster, work out the sines and cosines
of \fIphi\fR and \fItheta\fR, calling them \fIsph\fR, \fIsth\fR, \fIcph\fR
and \fIcth\fR.
.PP
For each point (\fIxs,ys\fR) evaluate the following temporary values:
.CD
.I
xg = xs - RADIUS + 0.5
yg = ys - RADIUS + 0.5

j = sqrt( xg*xg + yg*yg )
.PP
If \fIj\fR is greater than \fIRADIUS\fR then (\fIxs,ys\fR) is not a point
in the planet's image and should be ignored; set \fIxm = ym = -1\fR (or some
other null value). Otherwise,
.CD
.I
h = sqrt( DIST*DIST * ( g*g - j*j ) + g*g * j*j )
k = ( DIST*DIST - h ) / ( DIST*DIST + j*j )

xp = k * xg
yp = k * yg
zp = sqrt( g*g - xp*xp - yp*yp )
.R
.PP
(The vector \fI(xp,yp,zp)\fR, called \fIP\fR, can be used to
calculate illumination effects. See Section 6.2.)
.CD
.I
xt = xp*cth - yp*sth*cph + zp*sth*sph
yt = xp*sth + yp*cth*cph - zp*cth*sph
zt = yp*sph + zp*cph

w = sqrt( g*g - yt*yt )
alpha = acos( yt / g )
beta = acos( - xt / w )
.R
[\fIacos()\fR meaning 'inverse cosine']
.PP
All of these calculations use floating-point arithmetic. \fIxm\fR
and \fIym\fR, on the other hand,
are integers, and when converting from floating-point to integer values
in the next set of calculations
the 'integer part' of the number (the largest integer not greater than
that number) should be taken.
.CD
.I
xm = (int) beta * rho / pi
ym = (int) alpha * rho / pi

.R
[\fIpi\fR is (predictably enough) the constant 3.14159265(etc).
All the trigonometric calculations here operate in radians.]

.I
if xm = rho then let xm = rho - 1
if ym = rho then let ym = rho - 1
if zt < 0 then let xm = 2*rho - 1 - xm
.R
.PP
\fIxm\fR takes values from \fI0\fR to
\fI2*rho-1\fR and \fIym\fR takes values from \fI0\fR to \fIrho-1\fR.
These are the coordinates of a point on the mercator map of the planet's
surface.
.PP
The values of \fIxm\fR and \fIym\fR can now be stored in the Gush array.
.CD
.I
gush[ys][xs].xm_val = xm
gush[ys][xs].ym_val = ym
.R
.NH 2
The Line Gush
.PP
The Line Gush is all of the important data from the Square Gush
rearranged in such a way as to make the final animation as
fast as possible (this being where the name 'Gush' comes in).
.PP
The Line Gush takes the form of a one-dimensional array, a string of
values in the order they are used to draw the planet.
.PP
The actual format of the Line Gush is determined by the procedure
used to display the planet. Here is an example Line Gush format. For more
details see Sections 4 and 5.
.PP
The first entry in the Line Gush is the number of horizontal lines
needed to draw the planet, i.e., the planet's height in pixels.
It is equal to \fI2*RADIUS\fR.
.PP
Since the planet is circular, these horizontal lines will be
of different lengths.
The Square Gush treats all the lines as being of the same length and
fills in the gaps with 'null' entries.
These nulls are missed out when putting together the Line Gush.
.PP
Now, for each horizontal line of the planet (corresponding to each value
taken by \fIys\fR), the following values are stored in the Line Gush:
.IP (1) 5
The relative screen position of the start of the line.
Since the lines are all of different lengths, the Gush must provide
information on how to arrange them to give a circular shape. This
information will probably take the form of an amount
to be added to the screen address of the last point plotted
on the previous line to give the address of the first point to plot
on this new line.
.IP (2) 5
A function of the length of the line; this value determines
the number of points to plot. (For speed of animation,
it may be other than simply the number of points on the line.)
.IP (3) 5
For each point on the line, that point's \fIxm\fR and \fIym\fR values
(possibly combined into a single value).
.PP
It takes a considerable amount of time to create a full (Line) Gush
so it is advisable to save the completed data to disk rather than to create
new data each time.
.PP
There is no simple formula for the size of the Line Gush,
but in the above example it will be smaller than the Square Gush which
consists of \fI2*4*RADIUS*RADIUS\fR bytes (or words, depending on how
\fIxm\fR and \fIym\fR are stored).
.PP
An alternative approach is to create a Compiled Gush, an executable mixture
of data and machine code which allows for very fast animation, but which
takes up a large amount of memory.
.NH 1
Third Day Song
.NH 2
Making Planets
.PP
This part of the program creates a random, vaguely realistic-looking
planet surface which is something like fractally generated. (In my brief
search around the library I couldn't find any (comprehensible)
information about generating realistic spherical planet surfaces.)
.PP
The method used is as follows. The planet's surface (a sphere) is
cut around a random equator into two hemispheres. One of the
hemispheres is selected and the altitudes of all points on it increased or
decreased relative to the other hemisphere. This is repeated many
times with the relative changes in altitude gradually reducing in
significance.
.PP
This process acts on an array of altitude values called the Skin, which
describes in a two dimensional mercator map the spherical planet surface.
When the Skin is complete it is transformed into an array of colour
values called the Complexion. It is this which is used in the animation.
.NH 2
The Skin
.PP
The Skin is a two-dimensional array of size \fIrho\fR by \fI2*rho\fR
(this being the definition of the value \fIrho\fR), and each entry in it
represents the altitude of a point on the surface of the planet.
The Skin will be referred to by \fIskin[y][x]\fR
where \fIy\fR is the colatitude of a
point on the surface and takes values from \fI0\fR to \fIrho-1\fR, and
\fIx\fR is the longitude of a point on the surface and takes values
from \fI0\fR to \fI2*rho-1\fR. Note that the skin wraps around in the
\fIx\fR sense (so \fIx=2*rho\fR is equivalent to \fIx=0\fR), but not
in the \fIy\fR sense; \fIy=0\fR marks the north pole, \fIy=rho-1\fR marks
the south pole.
.PP
The elements in this array could be floating-point numbers, but, to
speed up calculations, it is probably best to use integers. All of the
altitude values are initially set to zero, or some other appropriate
base value.
.NH 2
The Riffs
.PP
To generate the planet's surface, the Skin must be treated as if it is
spherical when it is, in fact, flat. This is achieved with the help
of a set of data arrays, called the Riffs, which describe the shapes of
the possible fractures that can be made in the surface. The Riffs are
unchanging; the random planet surfaces (for fixed \fIrho\fR) are all
created using the same set of Riffs.
.PP
There are \fIrho/2\fR Riffs, numbered from \fI0\fR to \fIrho/2-1\fR, each
consisting of \fIrho/2\fR (again \fI0\fR to \fIrho/2-1\fR) integer values
between \fI0\fR and \fIrho/2\fR inclusive.
Let the Riffs be represented by \fIriff[A][t]\fR where \fIA\fR is the
Riff number and \fIt\fR is the position within that Riff.
.PP
The Riffs are generated in the following way with
\fIA\fR and \fIt\fR both taking values \fI0\fR to \fIrho/2-1\fR:
.CD
.I
omega = ( A + 0.5 ) * pi / rho
sigma = ( t + 0.5 ) * pi / rho
gamma = atan( tan(omega) * cos(sigma) )
riff[A][t] = rho/2 - round( gamma * rho / pi )
.R

[\fIround()\fR means 'to the nearest integer'.
\fIatan()\fR means 'inverse tangent'.]
.PP
It can take a little time to create all the Riffs, so it is not a bad idea
to save them to disk for future use.
.NH 2
The Song
.PP
This section describes the actual routine that generates the
planet's surface. It is fairly complicated.
.PP
For this part of the program the Skin (with all entries initially set to
zero), the Riffs, and the constant \fIrho\fR are required.
A couple of new constants also need to be defined.
.IP \fIFULL_BLAST\fR 12
This value determines the size of the fractures made in the
surface; it is the actual size of the first fracture made.
.IP \fIPOWER\fR 12
This constant controls the style of formation of the surface. A value of
1 results in mostly straight coastlines whilst a higher value gives
more jagged shapes. Try a value of 3, 4 or 5.
.PP
The number of 'strikes' used to make the surface (and hence the time taken)
is equal to \fIFULL_BLAST\fR to the power of \fIPOWER\fR. Something in
the order of several thousand strikes I find are needed to generate a
convincing surface.
.PP
The procedure that follows is written in an vague approximation of the
C language.
.ID
.I
FULL_BLAST = 20.0
POWER = 3.0

int skin[rho][2*rho];  /* Using integer altitude values */
int riff[rho/2][rho/2];  /* Riff data already generated */

int strike;  /* Number of fractures to make */
int displac = 0;  /* Move everything upwards; rebalance later */

int blast;  /* Depth of next fracture */
int rf_num;  /* Riff to use on this fracture */
int r1;  /* Preliminary random choice of riff */
int half;  /* Random choice of which half of surface to hit */
int dirn;  /* Random choice of whether to blast up or down */
int x_start;  /* Position around equator to start at */
float r2, dis;  /* Weight riff probabilities */

int x, y;  /* Every program needs some x and y coordinates */
int x1, x2, x3, x4;  /* A few spare x coordinates */


/* 'strike' is initially FULL_BLAST to the power of POWER */
/* We repeat until strike (decremented by one each time) is zero */
for ( strike = pow( FULL_BLAST, POWER ) ; strike > 0 ; strike-- ) {

    /* pow(A,B) means A to the power of B (A^B or A**B) */
    /* Watch out for conversions between 'int' and 'float' here */
    blast = FULL_BLAST / pow( strike, 1.0/POWER );

    /* Choose random values for next fracture */
    r1 = random(rho/2);  /* int from 0 to rho/2-1 (inclusive) */
    x_start = random(2*rho);  /* 0 to 2*rho-1 (inclusive) */
    half = random(2);  /* 0 or 1 */
    dirn = random(2);  /* 0 or 1 */
    r2 = ((float)rand())/(float)RAND_MAX;  /* between 0 and 1 */

    /* Balance choice of riffs evenly over the surface */
    /* (Avoids most fractures being along the equator) */
    dis = sin( pi * (r1+0.5) / rho );  /* All in floating-point */
    if ( r2 <= dis*dis ) rf_num = r1;
    else rf_num = rho/2 - 1 - r1;

    /* We only displace in the northern half of the planet */
    /* then make up for it at the end using 'displac' */
    if ( dirn == 0 ) blast = -blast;
    if ( half == 0 ) displac = displac - blast;

    /* This loop would be best converted to assembly language */
    /* The loop goes from x equal to 0 to x equal to rho/2-1 */
    /* Note: A%B means the remainder of A divided by B (A mod B) */
    /*       A+=B means A=A+B */
    for ( x = 0 ; x < rho/2 ; x++ ) {
        x1 = ( x_start + x ) % (2*rho);
        x2 = ( x_start + 2*rho-1 - x ) % (2*rho);
        for ( y = 0 ; y < riff[rf_num][x] ; y++ ) {
        /* If riff[rf_num][x] is zero this loop is not executed */
            skin[y][x1] += blast;
            skin[y][x2] += blast;
        }
        x3 = ( x_start + rho + x ) % (2*rho);
        x4 = ( x_start + rho-1 - x ) % (2*rho);
        for ( y = 0 ; y < rho-1 - riff[rf_num][x] ; y++ ) {
        /* If riff[rf_num][x] is rho-1 this loop is not executed */
            skin[y][x3] += blast;
            skin[y][x4] += blast;
        }
    }
}

/* Finally, shift all the altitudes to rebalance the zero level */
/* (This is not strictly necessary since altitudes are relative) */
for( y = 0 ; y < rho ; y++ ) for( x = 0 ; x < 2*rho ; x++ )
    skin[y][x]+=displac;
.R
.DE
.PP
This routine assumes that the Skin is made up of integer values
and so uses mostly integer variables. The advantages of using
ints rather than floats are that they use less
memory, they operate faster, and they allow the program to be
more easily converted into assembly language.
.PP
Bear in mind that integer variables can 'overflow' if they are required
to store very large numbers. If the program begins to produce unexpected
results, this could be the cause.
.NH 2
The Complexion
.PP
The Complexion is an array of the same size and shape as the Skin and
is referred to by \fIxion[y][x]\fR. Each entry in the Complexion is a colour
value and the array as a whole forms a coloured-in map of the planet's
surface.
.PP
The Complexion is derived from the Skin by assigning colours based on
the altitude at each point. A simple way to do this is as follows.
.PP
Choose a set of \fIK\fR colours such that colour \fI1\fR represents the
lowest altitude and colour \fIK\fR represents the highest altitude.
Look at the Skin to find the maximum and minimum altitude values
and divide up the range of altitudes into \fIK\fR equal-sized groups, each
corresponding to a colour. Then, if the maximum and minimum altitudes
are the values \fImax\fR and \fImin\fR,
.CD
.I
xion[y][x] = int{ ( skin[y][x] - min ) * K / (max-min+1) } + 1
.R
.PP
For a very simple planet design, colour any point with
an altitude of \fI(max+min)/2\fR or less sea-blue, and any other point
grass-green.
.NH 1
Notes on Implementation
.NH 2
Attachment to Hardware
.PP
The details of writing this program depend greatly on the hardware being
used: the CPU instruction set, the available memory, the graphics
specifications and the computer's speed, among other things.
.PP
In this section I'll sketch out how I envisage this program being
implemented to make the most of the hardware available.
.NH 2
Choice of Screen Mode
.PP
The way in which the screen memory of the computer is organised
determines to a large extent the structure of the animation routine.
.PP
The simplest way to write to the screen would be to use a function
of the type \fIplot(x_pos, y_pos, colour)\fR, but this would give
painfully slow animation. It is usually much better to write directly to
screen memory.
.PP
The nicest screen mode for this sort of animation would have each pixel
controlled by one byte of screen memory (suggesting a mode with 256 colours)
and would have consecutive pixels along a horizontal line corresponding to
consecutive bytes in memory, with the horizontal lines arranged in
order top to bottom. With other kinds of screen arrangement animation
routines become a little more tricky to put together.
.PP
Some screen modes use pixels which aren't exact squares, and this
results in planets that are elliptical instead of circular.
To compensate for this the \fI(xs,ys)\fR coordinates used in the Square
Gush have to be rescaled (the result being, in effect, a Rectangular Gush).
.PP
The choice of screen resolution is a balancing of two factors: for
planets of a fixed size, a low-resolution display gives a less detailed
image whilst a high-resolution display means slower animation.
A resolution of about 300 pixels by 200 pixels with a planet radius of
50 pixels (which is to say \fIRADIUS=50\fR) is a reasonable place to start.
.NH 2
Gush Structure
.PP
The amount of memory needed for the Gush depends on a lot of factors;
anything from two to ten bytes may be needed for each point to be plotted,
the number of which will be around \fIPI*RADUIS*RADIUS\fR.
A straightforward Line Gush for a planet with \fIRADIUS=50\fR and
\fIrho=128\fR may take up around 20k. A Compiled Gush for the same
planet may take up closer to 60k.
.PP
The value \fIDIST\fR has only a very slight effect on the appearance of the
planet. I usually give it a value somewhere in the thousands. It can
alternatively be omitted altogether: change the Gush calculations so that
\fIg=RADIUS\fR and \fIk=1\fR. This is equivalent to making \fIDIST\fR
infinitely large (and has the advantage of speeding up the Gush
calculations.)
.PP
As default values for \fIphi\fR and \fItheta\fR, try 45 and 30
degrees respectively.
.NH 2
Complexion Structure
.PP
The resolution of the planet's surface, \fIrho\fR, should be given a value
in compromise of two factors: if \fIrho\fR is not large enough the planet's
surface will be too blocky, but as \fIrho\fR becomes larger more memory is
required for the Complexion and more time is needed to generate a planet
surface. Also, very large values of \fIrho\fR give no obvious
improvement to the appearance of the planet.
.PP
In addition, the value of \fIrho\fR determines the number of different
frames seen when the planet is animated; the number of positions of
rotation the planet can be viewed in is equal to \fI2*rho\fR.
.PP
In general, \fIrho\fR can be given any value, but a value of \fI128\fR
may give certain advantages. Since the array \fIxion[y][x]\fR uses
values of \fIx\fR between \fI0\fR and \fI2*rho-1\fR and values of \fIy\fR
between \fI0\fR and \fIrho-1\fR, \fIrho=128\fR means that both \fIx\fR and
\fIy\fR values are byte-sized.
Also, the offset into the \fIxion\fR array is \fI2*rho*y+x\fR which
becomes \fI256*y+x\fR, so x and y are now the low order and high order
bytes of a CPU-friendly 16-bit word.
.PP
Each point in the Complexion is a colour value; if no more than 256
colours are used, then each entry in the array will take up one byte.
The total amount of memory used will then be \fI2*rho*rho\fR bytes.
.NH 1
Magrathea in Scattered Jumps: Plotting a Planet
.NH 2
Animation Routines
.PP
And so, at last, we arrive at the heart of the program: the animation routine.
.PP
What I'm going to do in this section is describe a progression of methods
for displaying planets, starting with simple routines to help explain the
process and then moving on to more effective methods.
.PP
Since the speed of the display routine is critical it will almost certainly
need to be written in assembly language. With this in mind, the descriptions
of the routines are in a fairly low-level pseudo-code.
.PP
Four bits of data are needed by the routines when displaying a planet:
.IP \fIxion\fR 6
The routine must have access to some Complexion data; the name \fIxion\fR
will be used to mean, depending upon the routine, either the entire
array \fIxion[y][x]\fR or the address in memory of (i.e., a pointer to)
the first byte in the array.
.IP \fIgush\fR 6
The routine needs Gush data of some description.
Like \fIxion\fR, \fIgush\fR will refer to either an array or a memory
address as the routine requires.
.IP \fIscr\fR 6
This value determines where on the screen the planet is displayed.
It could be either the x and y coordinates of a point on the screen
(referred to as \fIscr.x\fR and \fIscr.y\fR),
or the address of a point in screen memory.
The point in question will be the top-left 'corner' of the planet.
.IP \fIrot\fR 6
This is the state of rotation of the planet, the degree to which it appears
rotated about its axis when drawn. It is a value between \fI0\fR and
\fI2*rho-1\fR with wrap-around meaning that \fIrot=2*rho\fR is equivalent
to \fIrot=0\fR.
.NH 2
Using the Square Gush
.PP
This is the simplest of the display methods; it uses the Square Gush
as input, treating it as an array, and plots points to the screen using
a \fIplot\fR function.
This method could be implemented in a high-level language to
test how well the program works before going to the trouble of writing
a faster assembly language routine.
.PP
In addition to the parameters which are passed to the routine (see 5.1),
five local variables are used here: \fIys\fR and \fIxs\fR are the
coordinates of a point in the Gush and on the screen;
\fIcol\fR is the colour of the current point; \fIxm\fR and \fIym\fR are
values taken from the Gush data which refer to a point in the Complexion.
.PP
Remember that the Square Gush includes a number of 'null'
entries for which both \fIxm_val\fR and \fIym_val\fR are taken here to
be equal to \fI-1\fR.
.ID
.I
ys = 0
L1:
xs = 0
L2:

xm = gush[ys][xs].xm_val
ym = gush[ys][xs].ym_val
if ( xm = -1 ) and ( ym = -1 ) jump to L3
xm = ( xm + rot ) % (2*rho)
col = xion[ym][xm]
plot( (scr.x + xs), (scr.y + ys), col )

L3:
xs += 1
if ( xs != 2*RADIUS ) jump to L2
ys += 1
if ( ys != 2*RADIUS ) jump to L1
.R
.DE
.PP
It should be obvious roughly what this routine does. For each point in
an area of the screen, \fIxm\fR and \fIym\fR values are taken from the
corresponding point in the Square Gush.
If the point is valid (i.e., part of the planet) then a
colour value is derived from the Complexion and the point is plotted.
.PP
The value \fIrot\fR is added to \fIxm\fR, the result being trimmed so that it
remains between \fI0\fR and \fI2*rho-1\fR. In this way, the planet's
surface is effectively made to rotate around the planet. (This is the only
time that \fIrot\fR is used in the program.)
.PP
(Incidentally, 'A != B' means 'A not equal to B' and 'A % B'
means 'remainder of A divided by B'.)
.NH 2
Using the Line Gush
.PP
Because the Line Gush does not include the 'null' entries of the Square Gush,
a routine using it can run faster. The Line Gush is a sequence of values
in memory which are accessed in order. The notation \fIx=[gush++]\fR will
be used to mean 'load the next Gush value into \fIx\fR' - the variable/register
\fIgush\fR holds the address of the next value to be used; this value is
loaded into \fIx\fR and \fIgush\fR is incremented by an appropriate amount.
.PP
The format of the Line Gush is defined by the structure of the routine.
In this example, the first value is the total number of lines to draw and
is followed by the appropriate data for each line consisting of:
.IP (1) 5
An amount to add to or subtract from \fIscr.x\fR, the x-coordinate of the next
point to be plotted, so that this line is drawn to fit the circular shape
of the planet.
.IP (2) 5
The number of points to be plotted on this line.
.IP (3) 5
For each point on this line, a value for \fIxm\fR followed by a value
for \fIym\fR.
.PP
The local variables used in this routine are the same as those used in
Section 5.2 except that \fIxs\fR and \fIys\fR are renamed \fIxcount\fR
and \fIycount\fR to reflect their slightly different application.
.ID
.I
ycount = [gush++]
L1:
scr.x += [gush++]
xcount = [gush++]
L2:

xm = [gush++]
ym = [gush++]
xm = ( xm + rot ) % (2*rho)
col = xion[ym][xm]
plot( scr.x, scr.y, col )
scr.x += 1

xcount -= 1
if ( xcount != 0 ) jump to L2

scr.y += 1
ycount -= 1
if ( ycount != 0 ) jump to L1
.R
.DE
.PP
Note that the value of \fIRADIUS\fR is no longer needed here - all the
required data is stored in the Gush.
.NH 2
Screen Memory Addresses
.PP
The most obvious way of increasing the speed of the previous routine
is to avoid using the \fIplot\fR function and to instead write directly
to the screen memory.
.PP
Section 4.2 lists the assumptions I am making about the layout
of the screen memory. The variable/register named \fIscr\fR will now
hold the memory address of the next point of the screen to be altered.
The notation \fI[scr]=x\fR will be used to mean that the byte or word
at screen memory address \fIscr\fR is to be loaded with the value \fIx\fR.
.PP
Apart from \fIscr\fR, the only other difference between this routine and
the last one is in the Line Gush: the value which before
was added to \fIscr.x\fR is now added to \fIscr\fR. This new value is
the difference between the address of the last point on the previous
line of the planet and the address of the first point on the new line of
the planet.
.ID
.I
ycount = [gush++]
L1:
scr += [gush++]
xcount = [gush++]
L2:

xm = [gush++]
ym = [gush++]
xm = ( xm + rot ) % (2*rho)
col = xion[ym][xm]
[scr] = col
scr += 1

xcount -= 1
if ( xcount != 0 ) jump to L2
ycount -= 1
if ( ycount != 0 ) jump to L1
.R
.DE
.NH 2
Games with Xion
.PP
All of the routines so far have treated \fIxion\fR as an array; in a
low-level language the address in memory of a value is needed instead
of its position in the array, so we replace the line
.CD
.I
col = xion[ym][xm]
.R
.DE
.LP
with the line
.CD
.I
col = [ xion + 2*rho*ym + xm ]
.R
.DE
.PP
(This assumes that one byte is used for each of the values in the
Complexion.)
.NH 3
.PP
The use of \fIxm\fR and \fIym\fR to point to values in the Complexion
is somewhat inefficient. One fairly simple way of speeding the process
up would be to store the value of \fI2*rho*ym\fR or even
\fIxion+2*rho*ym\fR in the Gush instead of just \fIym\fR.
The modulus ('%') calculation can also be made faster by
choosing a value for \fIrho\fR that is a power of two; then the modulus
operation can be replaced by a logical AND operation which most
microprocessors can perform much faster. If this is done then the
central loop of the routine will look something like:
.ID
.I
xm = [gush++]
ym2 = [gush++]
xm = ( xm + rot ) AND (2*rho-1)
col = [ ym2 + xm ]
[scr] = col
scr += 1
.R
.DE
.NH 3
.PP
An alternative approach can be used on CPUs which allow their 16- or
32-bit registers to be split into component 8-bit registers. Suppose one
complete register is called \fIyyxx\fR and that its lowest 8 bits
can be operated upon separately as the register \fIxx\fR.
Since \fIxx\fR is only 8 bits long, the equivalent of an \fIAND 255\fR
operation is automatically performed on it whenever it is used.
Thus if \fIrho\fR is set equal to 128 and the Gush holds the combined value
\fI2*rho*ym+xm\fR instead of both \fIxm\fR and \fIym\fR, then the core
of the routine is simply:
.ID
.I
yyxx = [gush++]
xx += rot
col = [ xion + yyxx ]
[scr] = col
scr += 1
.R
.DE
.NH 3
.PP
There is yet a third way to simplify the routine, though it requires
twice as much memory for the Complexion data.
An expanded Complexion is created in which each line of the map appears
twice: Line 1 is followed in memory by another
copy of Line 1 before getting to Line 2, such that \fI[xion]\fR is the
same as \fI[xion+2*rho]\fR, \fI[xion+1]\fR is the same as
\fI[xion+2*rho+1]\fR, and so on up until \fI[xion+4*rho]\fR which is the
start of the second line.
.PP
An expanded Complexion removes the need for the modulus ('%')
calculation when \fIrot\fR is added on to \fIxm\fR.
.PP
Instead of the two values \fIxm\fR and \fIym\fR being used for each
point in the Line Gush, the single combined value \fIxion+4*rho*ym+xm\fR
(or possibly just \fI4*rho*ym+xm\fR) is used. The single
variable/register \fIymxm\fR replaces both \fIxm\fR and \fIym\fR
and the core of the routine now becomes:
.ID
.I
ymxm = [gush++]
col = [ ymxm + rot ]    ( \fRor\fI [ xion + ymxm + rot ]  )
[scr] = col
scr += 1
.R
.DE
.PP
(Note that \fI4*rho\fR now replaces \fI2*rho\fR as the width of the
Complexion array.)
.NH 2
Scattered Jumps
.PP
There is another aspect of the display routine which can still be made
more efficient: the looping mechanism. For every point of the planet that is
plotted, additional instructions must be executed to loop back to plot the
next point. These time wasting loop instructions can be missed out by
repeating the plotting code in memory once for each of the points to be
plotted.
.PP
The problem with this is that the number of points to be plotted on each
line varies. The solution is to miss out some of the plot routines
by jumping past them - this needs an 'indirect' jump instruction, the
address to jump to being stored in a register or in memory.
.PP
The following code shows how this method could be implemented into a
display routine. It is based around an expanded Complexion, as described
in the previous sub-section. The value in the Gush which used to be the
number of points to plot on this line is now an address to jump to in
order to plot that number of points.
.ID
.I
ycount = [gush++]

L1:
scr += [gush++]
jump to [gush++]

[...]

* ymxm = [gush++]
* col = [ ymxm + rot ]
* [scr] = col
* scr += 1

ycount -= 1
if ( ycount != 0 ) jump to L1
.R
.DE
.PP
The code marked by the asterisks plots one point. Assuming that
\fIMAX_R\fR is the largest value of \fIRADIUS\fR ever likely to be used
in the program, then the asterisked code needs to be repeated
\fI2*MAX_R\fR times. The complete routine should take up no more than a
few kilobytes.
.NH 2
The Compiled Gush
.PP
This is a way by which the animation can be dramatically increased
in speed (and thanks to Jamie Lokier for pointing this out): instead of the
Gush containing numerical data to be read by an animation routine, it
can itself be an executable routine with the data hard-wired into it.
.PP
The Square Gush is translated directly into machine code, with a few
bytes of code for each of the points to be plotted. A section of the
Compiled Gush (working with an expanded Complexion) would then look
something like:
.ID
.I
col = [ m1 + rot ]
[scr] = col
scr += 1

col = [ m2 + rot ]
[scr] = col
scr += 1

col = [ m3 + rot ]
[scr] = col
scr += 1

[...]
.R
.DE
.LP
where \fIm1\fR, \fIm2\fR and \fIm3\fR are immediate (constant) values.
.PP
The Compiled Gush also contains machine instructions to
move \fIscr\fR from the end of one line to the start of the next, and, of
course, a 'return' instruction at the end. (Furthermore, quite a bit of
optimization can often be done on the code as it is generated.) The planet
is then animated simply by choosing values for \fIscr\fR and \fIrot\fR
and calling the Compiled Gush code.
.PP
But there is one big drawback to this: a Compiled Gush takes up a
lot of memory, several times more than a normal Gush. Fast animation is
what this method delivers, but it does so at the cost of a large chunk
of memory.
.NH 1
Finishing Off
.NH 2
Putting Together the Pieces
.PP
Way back at the beginning of all this I described the animation program
as consisting of three basic parts. The code for creating Gush data
is detailed in Section 2, the code for creating Complexion data is
detailed in Section 3, and Section 5 constructs a routine that draws a
planet using these two data arrays.
.PP
In Section 1.4, constant values (\fIrho\fR, \fIRADIUS\fR,
\fIDIST\fR, etc.) are introduced. Whatever values these constants are
given it is important that they remain the same in all parts of the
program.
.PP
With all segments of the program complete an animation can
finally be put together. The simplest animation, that of a planet spinning
in the centre of the screen, is accomplished in the following way.
.PP
Create a Gush and a Complexion, storing both in files on disk. Write a
simple piece of code that first loads in both data files and then, with an
appropriate value for \fIscr\fR (the point on the screen where the
planet is to appear), repeatedly calls the display routine. The
additional parameter \fIrot\fR is increased (or decreased) by a
small, fixed amount on each call with a modulus operation keeping it in the
range \fI0\fR to \fI2*rho-1\fR.
.PP
There is not much more to say about the animation; further elaborations
are left to the programmer's imagination. As a few suggestions:
.IP  *
Store several different Gushes on disk and select one to use at
random when the animation is run. The Gushes are all created using
different values for \fIphi\fR and \fItheta\fR (and possibly
\fIRADIUS\fR).
.IP  *
Use different sets of colours for different planets; choose the set
to be used at random when converting a Skin to a Complexion.
.IP  *
Make more interesting planet surfaces; add random cloud and mountain
generation, or edit a Complexion using a standard bitmap editor to give
it a smiling face.
.IP  *
Draw a star field behind the planet (to make the fact that it's supposed to
be a planet more obvious!). Animate the star field.
.IP  *
Shade the planet (as described in the next sub-section).
.IP  *
Before displaying the next frame of the planet, delete the old frame and
change the value of \fIscr\fR so that the planet appears in a different
place. Make the planet move. Make it bounce!
.NH 2
Illumination
.PP
In Section 2.3, when calculating values for the Gush a vector
\fIP=(xp,yp,zp)\fR is generated for each point \fI(xs,ys)\fR. This
vector can be used to give a basic illumination effect, that of
light shining onto the planet from a fixed direction.
.PP
For this effect to work, some method for selectively altering the
brightness of the pixels making up the planet's image is needed. Ideally,
each pixel should have a collection of bits controlling its brightness
which are independent of the bits controlling its colour. The planet can
then be shaded by adjusting just these brightness bits.
.PP
Define a vector \fII=(xi,yi,zi)\fR as the direction from which
light falls onto the planet. Then, for each \fI(xs,ys)\fR, calculate
a value \fIlambda\fR as follows:
.CD
.I
q = sqrt( xi*xi + yi*yi + zi*zi )

lambda =  ( I . P ) / ( |I| * |P| )
= ( xi*xp + yi*yp + zi*zp ) / ( q * g )
.R

(The calculation of the constant \fIg\fR is described in Section 2.3)
.DE
.PP
\fIlambda\fR is a measure of the illumination of the point \fI(xs,ys)\fR
and takes values from -1 (minimum brightness) to +1 (maximum brightness).
(Strictly, if \fIlambda\fR's value is below zero, then no light at all
reaches \fI(xs,ys)\fR - it is on the dark side of the planet.)
.PP
Transform each \fIlambda\fR into a number \fIkappa\fR, the
value to be put in the brightness bits of the pixel at (\fIxs,ys\fR).
To avoid the shading of the planet being too regular, add a slight
random influence to the transformation such as changing the value
of \fIlambda\fR by a small, random amount. This blurs the border
between 'light' and 'dark' regions of the planet.
.PP
Illuminating the planet is now a matter of keeping the brightness of
each pixel fixed (at the value \fIkappa\fR) whilst allowing the
planet display routine to fill in the pixel's colour.
.PP
One way of doing this would be to set each pixel to brightness
\fIkappa\fR and colour zero, and then use a logical OR operation in the
display routine to overlay colours onto the pixels. Before drawing the
next frame, the colour of each pixel would need to be reset to zero,
either by rewriting all brightness and colour values together, or by
resetting just the colour bits using multiple logical AND operations.
.NH 2
Whys and Wherefores
.PP
That's about it really. The one thing left to add is an
explanation. I've written some seven thousand words describing how to
put together a pretty but pointless animation. Why did I bother?
.PP
Well, as I said earlier, nearly all of the mildly clever animation
techniques used here I've had to work out for myself. They aren't the
sort of thing that you commonly find in text books. In a way this
document is a small attempt to change that - it's sort of a "Beginner's
Guide to Real-time Animation (Volume 1: Things That Bounce)".
.PP
Also, there's a limit to the number of things that I can think of
to do to spinning planets. I want to see what ideas other people come up
with using this as a starting point.
.PP
So, having read this document, if you're interested in bringing this
animation to life, go to it, and good luck to you.
.NH 2
Acknowledgements
.PP
Thanks must go to Matt Spinner for helping create the original planet
demo and to everyone else who was around at the time (Dave, Nick,
Simon, Phill, JT, etc).
.PP
And thanks also to Jay Dresser and Jamie Lokier from Usenet for comments
on the original posting.